The present invention relates to a novel operator for decoding block and convolutional codes in digital communications systems and particularly for simplifying log-MAP decoding of block and convolutional codes. The operator, the avg* representation of a kernel operation, may allow log-MAP decoding of many information services. The invention also relates to a low-complexity implementation of generating an optimal log-likelihood ratio (LLR) for use in decoders such as block and convolutional decoders.
Block and convolutional codes, which have been advantageous in digital communications systems, are among some techniques used to transport information reliably. A variety of methods can be used to decode block and convolutional codes and to recover the information. For example, one method is a Viterbi algorithm, which is a maximum-likelihood decoding method that minimizes the probability of word error. Since a word is comprised of a sequence of symbols (or bits), the Viterbi algorithm is often called a sequence estimator. The Viterbi algorithm however does not minimize the probability of symbol (or bit) error. Another method for decoding block and convolutional codes uses a maximum aposterio (MAP) principle. MAP decoders make optimum symbol-by-symbol decisions, as well as providing xe2x80x9csoftxe2x80x9d reliability information which, for example, is desired in concatenated decoding systems such as turbo decoders. A possible algorithm for MAP decoding is the Bahl, Cocke, Jelink, and Rajiv (BCJR) algorithm. While the BCJR algorithm is the most commonly used MAP algorithm, the BCJR algorithm however suffers several shortcomings that make it difficult for hardware and software implementations, e.g., the requirement for multiplications and exponentiations.
In general, a MAP decoder requires forward and backward generalized Viterbi recursions on the code trellis, requiring sums of products of probabilities. A MAP decoder also computes likelihood ratios that are based on the results of the forward and backward recursions. The log-MAP algorithm couches the MAP decoder in the logarithmic domain, eliminating exponentiations and turning the products into sums, but also turning the sums into operations of a complicated function (i.e., log-add). This complicated function is the kernel operation of the log-MAP decoder that dominates the overall decoder complexity, similar to the add-compare-select (ACS) operation in a conventional Viterbi decoder. In the art, the complicated function has been represented as the max* function, a maximization (max) operation plus a correction term. One common implementation method for the max* function computes the max and adds a correction term which is accessed from a lookup table. Although this method appears to be efficient, the table lookup may be too complex to implement in both software and hardware. For example, table lookups may cause pipeline stalls within processors. One sub-optimal implementation, known as a max-log-MAP function, omits the correction term (i.e., max instead of max*).
One class of block and convolutional codes is a turbo code, which is, for example, being proposed for third generation (3G) cellular services. The decoders for turbo codes (turbo decoders) can be difficult to implement because they are complex and because the decoder is iterative. For instance, complexity estimates for turbo decoding 3G services can prohibit optimal (MAP or log-MAP) decoding of the constituent codes that comprise a turbo code. Although a sub-optimal algorithm such as the max-log-MAP or Soft Output Viterbi Algorithm (SOVA) may be used to meet the complexity constraints, either the decoder performance suffers from not using the optimal algorithm or number of iterations required to meet a specified performance increases. Therefore, there is a need for an algorithm that allows computationally efficient log-MAP decoding.
Many current (EDGE, iDEN) and most future (1XTREME, HDR, 4G) communication systems are employing higher-order modulations (8PSK, 16QAM, 64QAM, etc) in order to improve system spectral efficiency. Soft-decision decoding in these systems is complicated by the need for soft values for each encoded bit, rather than each symbol. Soft-decision decoding is necessary because of improved reliability to voice and data (up to 2 dB) and it facilitates advanced decoding techniques such as turbo codes and hybrid ARQ. The optimal soft value for bit k of a received symbol y, for any set of possible modulated (transmitted) symbols X, is:                                           ln            ⁢                          xe2x80x83                        ⁢                          (                                                p                  ⁢                                      xe2x80x83                                    ⁢                                      (                                                                  y                        |                        x                                            ,                                              x                        ∈                                                  X                          0                                                                                      )                                                                    p                  ⁢                                      xe2x80x83                                    ⁢                                      (                                                                  y                        |                        x                                            ,                                              x                        ∈                                                  X                          1                                                                                      )                                                              )                                =                      ln            ⁢                          xe2x80x83                        ⁢                          (                                                                    ∑                                          X                      0                                                              xe2x80x83                                                        ⁢                                      xe2x80x83                                    ⁢                                      p                    ⁢                                          xe2x80x83                                        ⁢                                          (                                              y                        |                        x                                            )                                                                                                            ∑                                          X                      1                                                              xe2x80x83                                                        ⁢                                      xe2x80x83                                    ⁢                                      p                    ⁢                                          xe2x80x83                                        ⁢                                          (                                              y                        |                        x                                            )                                                                                  )                                      ,                            (        1        )            
where x is a modulated symbol, Xi={x|xk=i}, and xk is the corresponding kth bit of the modulated symbol index for x, and all symbols are equally probable. Because equation (1) is complex to implement, sub-optimal methods of generating soft values are employed. The current method of generating soft values is the dual-min,       K    ⁢          xe2x80x83        ⁢          (                                    min                          X              1                                ⁢                      xe2x80x83                    ⁢                      d            1            2                          -                              min                          X              0                                ⁢                      xe2x80x83                    ⁢                      d            0            2                              )        ,
where K is a scale factor proportional to the signal-to-noise ratio (SNR), X1 is the set of constellation points with a xe2x80x9c1xe2x80x9d in the desired bit position, and X0 is the set of constellation points with a xe2x80x9c0xe2x80x9d in the desired bit position. The term d12 (d02) is the squared Euclidean distance from the received symbol to the constellation symbol with a 1 (0) in the desired position. The dual-min essentially compares the received symbol to all possible transmitted symbols, and assigns a soft value based only on the closest symbol with a 0 and the closest symbol with a 1 in that bit position. The dual-min is much easier to implement than the optimal method, but it unfortunately suffers a performance degradation from the optimal method.
Thus, there is also a need for a low-complexity, high-performance method of generating bit soft values from higher-order modulation symbols.